package 链表题目;

import 链表题目.model.ListNode;


// 分割链表
// https://leetcode.cn/problems/partition-list/
class 分割链表 {
    public ListNode partition(ListNode head, int x) {
        // 一个指针记录 < x节点的位置
        ListNode small = new ListNode(0, null);
        // 一个指针记录 >= x节点的位置
        ListNode big = new ListNode(0, null);
        // 答案
        ListNode ans = new ListNode(0, small);
        ListNode bigHead = new ListNode(0, big);
        while (head != null) { // x = 3
            if (head.val < x) {
                small.next = head;// 1 -> 2 -> 2
                small = small.next;
                // 记录当前位置，即上一个位置
            } else {
                // 大于等于x就不处理后移
                big.next = head; // 4 -> 3 -> 5
                big = big.next;
            }
            head = head.next;
        }
        big.next = null;
        small.next = bigHead.next.next;
        return ans.next.next;
    }

//    public static void main(String[] args) {
//        ListNode one6 = new ListNode(2, null);
//        ListNode one5 = new ListNode(5, one6);
//        ListNode one4 = new ListNode(2, one5);
//        ListNode one3 = new ListNode(3, one4);
//        ListNode one2 = new ListNode(4, one3);
//        ListNode one1 = new ListNode(1, one2);
//    }
}
